免费道路
Time Limit: 2 Sec Memory Limit: 128 MB
Description
Output
5 7 2
1 3 0
4 5 1
3 2 0
5 3 1
4 3 0
1 2 1
4 2 1
Sample Output
3 2 0
4 3 0
5 3 1
1 2 1
HINT
1<=n<=20000,1<=m<=100000,0<=k<=n-1
Main idea
一种0边,一种1边,求一棵最小生成树并且正好有K条0边,输出其中一种方案。
Solution
显然要搞一棵符合题目的生成树。
每次要加入0边或者1边,直接做肯定不可行,考虑有什么0边是一定要加入的。
只需要输出一种方案,所以我们先加入所有可加的1边,如果图不联通则加入可加入的0边,那么这几条0边在我们所求的方案中是一定需要加入的。
这时候判断一下,如果此时加入的0边数量>K,或者图还是无法联通的话则无解。然后处理完毕前半部分,考虑接下来如何实现。
因为我们要使得图为树并且正好有K条0边,运用贪心,想到了加入0边到K条位置(如果到不了K条则也无解),然后剩下的用1边来填。
验证一下这样做的可行性:由于我们在前半部分使得了可以成为一棵树,那么显然我们在后半部分中每加入一条0边,则在前半部分中一定有一条1边可以替换使得可行(因为前半部分是尽量加入1边)。每次连边判环运用Kruscal即可。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114
| #include<bits/stdc++.h> using namespace std;
const int ONE=1000001; const int INF=2147483640;
int n,m,k; int Edge_k; int fa[ONE]; int num; int Choose[ONE]; int ans_num; int the0;
struct power { int x,y,v; }a[ONE],Ans_edg[ONE];
int get() { int res,Q=1; char c; while( (c=getchar())<48 || c>57) if(c=='-')Q=-1; if(Q) res=c-48; while((c=getchar())>=48 && c<=57) res=res*10+c-48; return res*Q; }
int find(int x) { if(fa[x]!=x) fa[x]=find(fa[x]); return fa[x]; }
void Un(int a,int b) { int a1=find(a); int b1=find(b); if(a1!=b1) fa[a1]=b1; }
int Add_set(int N,int v,int ci) { int kd=0; for(int i=1;i<=m;i++) { if(kd>=N) break;
if(a[i].v!=v) continue;
int x=a[i].x,y=a[i].y; if(find(x)!=find(y)) { Un(x,y); if(ci>=2) Ans_edg[++ans_num]=a[i]; if(ci==2) { Choose[++num]=i; } Edge_k++; kd++; if(ci==3) the0++; } if(Edge_k==n-1) break; } }
int main() { n=get(); m=get(); k=get(); for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++) { a[i].x=get(); a[i].y=get(); a[i].v=get(); } Edge_k=0;
Add_set(INF,1,1); Add_set(INF,0,2);
if(Edge_k<n-1 || num>k) { printf("no solution\n"); return 0; }
Edge_k=0; for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=num;i++) { int x=Choose[i]; Un(a[x].x,a[x].y); Edge_k++; if(Edge_k==n-1) break; }
Add_set(k-num,0,3); if(the0!=k-num) { printf("no solution\n"); return 0; }
Add_set(INF,1,4); for(int i=1;i<=ans_num;i++) { printf("%d %d %d\n",Ans_edg[i].x,Ans_edg[i].y,Ans_edg[i].v); }
}
|